格倫布編碼

編碼對象

非負整數(0、正整數)

對數字進行分組

1. 決定每組有幾個數字
   例如：每組有10個數字

2. 用除法對數字進行分組
   例如：數字42，第4組第2個
   42 / 10 = 4
   42 % 10 = 2

第幾組的編碼方式

第幾個的編碼方式

每組10個，可能的餘數為0 ~ 9
使用二進位編碼

用4bit去編碼，有的編碼沒有使用到

因為4bit編碼沒有全部用完
有的數字以3bit編碼
有的數字以4bit編碼

沒用到的編碼的數量 2^4 - 10 = 6
前6個數字(0 到 5) 以3bit編碼
其他數字，仍然以4bit編碼

解碼的時候，先讀取3bit

如果3bit的數值小於沒有使用的空間 6
　　第幾個 = 3bit的數值
否則
　　需要再讀取1bit

現在的問題是：4bit數字的前3bit小於6
在解碼的時候，它就不會再讀取1bit

解法：使用別的4bit數字
新的4bit數字 = 舊的4bit數字 + 6

編碼結果

數字42，它位於第4組第2個
它的格倫布編碼
11110010

解碼步驟

第幾組

先看看有幾個1
遇到0之前，總共有幾個1

第幾個

每組個數 = 10
10不是2的次方(例如：2^1、2^2、2^3)
位於 2^3 到 2^4 之間
使用3bit或4bit編碼
沒有使用的空間 = 2^4 - 10 = 6

先讀取3bit的數值
如果3bit的數值小於沒有使用的空間 6
　　第幾個 = 3bit的數值
否則
　　再讀取1bit
　　第幾個 = 4bit的數值 - 沒有使用的空間 6

解碼結果

11110010
原數字 = 第4組 * 每組個數 10 + 第2個 = 42

指數哥倫布編碼

編碼步驟

1. 數字 → 第幾個數字
   以數字9為例
   它是第10個數字(最前面的數字是0)
   10的二進位是 1010

2. 補0
   最高位bit 一定是1
   其他位bit的長度 3
   在1010前面補3個0
   補3個0的意思

   1. 在解碼的時候
      遇到1之後，要繼續讀取3bit

   2. 表示數字9位於第3組

編碼結果

數字9的指數哥倫布編碼為
0001010

0到15的指數哥倫布編碼

每組個數不一樣

每組第0個的指數哥倫步編碼

第2組第0個 = 第4個數字
100 = (第1組個數 + 第0組個數) + 1
　　= (2^1 + 2^0) + 1
　　= 4

第3組第0個 = 第8個數字
1000 = (第2組個數 + 第1組個數 + 第0組個數) + 1
　　= (2^2 + 2^1 + 2^0) + 1
　　= 8

解碼步驟

數字9的指數哥倫布編碼為
0001010

先看看有幾個0

遇到1之前，總共有幾個0

3個0表示
遇到1之後，要繼續讀取3bit

讀取完的結果

1010(二進位) = 10(十進位)

第10個數字 = 數字9
10 - 1 = 9

0階指數哥倫布編碼

前面介紹的，就是0階指數哥倫布編碼
數字9的0階指數哥倫布編碼為
0001010

1階指數哥倫布編碼

以數字9為例

1. 先轉成二進位
   1001

2. 因為是1階，把最低1bit暫時刪除
   100

3. 把100去做0階指數哥倫布編碼
   100 → 數字4 → 第5個數字 → 101
   補0之後，得到 00101

4. 把刪除的1bit補回來
   數字9的1階指數哥倫布編碼
   001011

5. 解碼
   遇到1之前，總共有幾個0
   讀取了001
   總共有2個0
   本來要繼續讀取2bit
   但是，因為它是1階指數哥倫布編碼
   所以，遇到1之後，繼續讀取 (2 + 1) bit
   讀取的結果為
   001011

解碼方法1
001011
　↓　暫時刪除1bit
00101
　↓　減1
00100
　↓　補回1bit
001001
　↓
　9

解碼方法2
001011 (二進位) = 11 (十進位)
因為是1階指數哥倫布編碼
11 - 2^1 = 9

0階vs1階指數哥倫布編碼

參考資料

• Python - Golomb Encoding for b=2n and b!=2n - GeeksforGeeks

• H.264学习笔记6——指数哥伦布编码 - DwyaneTalk - 博客园

• 格倫布編碼 - 維基百科，自由的百科全書

• 指數哥倫布碼 - 維基百科，自由的百科全書

• Golomb coding – Gea-Suan Lin's BLOG